public class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if (A == null || B == null) return false;
        return isSame(A, B) || isSame(A.left, B) || isSame(A.right, B);

    }
    public boolean isSame(TreeNode a, TreeNode b) {
        if (a == null && b == null) return true;
        else if (a != null && b != null && a.val == b.val) return isSame(a.left, b.left) && isSame(a.right, b.right);
        else return false;
    }
}

/*上面的是错的*/
class Solution2 {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if (A == null || B == null) return false;
        return isContain(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);
    }

    public boolean isContain(TreeNode a, TreeNode b) {
        if ( b == null) return true;
        else if (a != null && a.val == b.val) return isContain(a.left, b.left) && isContain(a.right, b.right);
        else return false;
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}